package com.xj.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 有效的括号
 */
public class L20_括号对是否合法 {

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：
     * <p>
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     * <p>
     * 示例 1:
     * 输入: "()"
     * 输出: true
     * <p>
     * 示例 2:
     * 输入: "()[]{}"
     * 输出: true
     * <p>
     * 示例 3:
     * 输入: "(]"
     * 输出: false
     * <p>
     * 示例 4:
     * 输入: "([)]"
     * 输出: false
     * <p>
     * 示例 5:
     * 输入: "{[]}"
     * 输出: true
     */

    public static void main(String[] args) {
        System.out.println(isValid("()"));
        System.out.println(isValid("()[]{}"));
        System.out.println(isValid("(]"));
        System.out.println(isValid("([)]"));
        System.out.println(isValid("{[]}"));
    }

    //自己的解法：1个栈,匹配才弹出
    public static boolean isValid(String s) {
        Stack<String> stack = new Stack();

        int length = s.length();
        for (int i = 0; i < length; i++) {
            String tmp = s.substring(i, i + 1);
            if (tmp.equals("(") || tmp.equals("[") || tmp.equals("{")) {
                stack.push(tmp);
            } else {
                if (stack.empty()) {
                    return false;
                }
                String top = stack.peek();

                if ((top.equals("(") && tmp.equals(")")) ||
                        (top.equals("[") && tmp.equals("]")) ||
                        (top.equals("{") && tmp.equals("}"))) {

                    stack.pop();
                    continue;
                }
                return false;
            }
        }
        return stack.empty() ? true : false;
    }

    //官方最优解：使用hashmap来替换if关系
    public static boolean isValidOffice(String s) {
        Map<Character,Character> map=new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (map.containsKey(c)) {
                //弹出来之后就不会放回去了，要么错误，要么成功开始下一个字符
                char topElement = stack.empty() ? '#' : stack.pop();
                if (topElement != map.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
